package 回溯;
//https://leetcode.cn/problems/surrounded-regions/
import sun.misc.Queue;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class 被围绕的区域 {
    int[] x = new int[]{-1 , 0 , 0 , 1};
    int[] y = new int[]{0 , -1 , 1 , 0};
    public void solve(char[][] board) {
        //先处理边界，如果边界是o，与o相连的肯定不是被包围的，处理完之后剩下的o就是被包围的
        for (int i = 0 ; i < board.length ; i++){
            if (board[i][0] == 'O'){
                fun_DFS(board , i , 0);
            }
            if (board[i][board[0].length - 1] == 'O'){
                fun_DFS(board , i , board[0].length - 1);
            }
        }
        for (int i = 0 ; i < board[0].length ; i++){
            if (board[0][i] == 'O'){
                fun_DFS(board , 0 , i);
            }
            if (board[board.length - 1][i] == 'O'){
                fun_DFS(board , board.length - 1 , i);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'Z'){
                    board[i][j] = 'O';
                }
            }
        }
    }
    public void fun_DFS(char[][] board , int gx , int gy){
        if (board[gx][gy] == 'O'){
            board[gx][gy] = 'Z';
        }
        for (int i = 0 ; i < 4 ; i ++){
            int nx = gx + x[i];
            int ny = gy + y[i];
            if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length && board[nx][ny] == 'O'){
                fun_DFS(board , nx , ny);
            }
        }
    }
    public void fun_BFS(char[][] board , int gx , int gy){
        //这里没优化，在LeetCode上一些数据内存会不够用，可以尝试优化一下
        Deque<Point> que = new LinkedList<>();
        if (board[gx][gy] == 'O'){
            board[gx][gy] = 'Z';
        }
        que.offer(new Point(gx , gy));
        while (!que.isEmpty()){
            Point point = que.poll();
            for (int i = 0 ; i < 4 ; i ++){
                int nx = point.x + x[i];
                int ny = point.y + y[i];
                if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length && board[nx][ny] == 'O'){
                    que.offer(new Point(nx , ny));
                }
            }
        }
    }
    //辅助BFS的点类
    public class Point{
        int x;
        int y;

        public Point() {
        }
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
